package test230602;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/2 22:30
 * 152. 乘积最大子数组
 * https://leetcode.cn/problems/maximum-product-subarray/
 */
public class Solution03 {

    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];  // f[i] 表示以 i 位置结尾的子数组的最大乘积
        int[] g = new int[n];  // g[i] 表示以 i 位置为结尾的子数组最小乘积(用于处理负负得正的情况)
        int maxVal = nums[0];  // 记录最优结果
        f[0] = g[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            f[i] = Math.max(Math.max(f[i-1] * nums[i], g[i-1] * nums[i]), nums[i]);
            g[i] = Math.min(Math.min(f[i-1] * nums[i], g[i-1] * nums[i]), nums[i]);
            maxVal = Math.max(maxVal, f[i]);
        }
        return maxVal;
    }
}
